Linear propagator

Linear propagator
View static image
Pattern type	Puffer
Number of cells	290096
Bounding box	14826990 × 14826908
Direction	Orthogonal
Period	237228617
Speed	256c/237228617
Discovered by	Dave Greene
Year of discovery	2013
Pattern files Macrocell linearpropagator.mc Zip archive linearpropagator.zip

Linear propagator is any of the three self-constructing puffers built by Dave Greene and published on November 23, 2013. It is arguably the first explicit example of a replicator in Conway's Game of Life, depending on the exact definition of "replicator".

As the pattern is too big to be displayed in detail using any reasonable scale (given one pixel were 1 mm, the whole pattern would be almost 15 km wide), the image on the right depicts only the underlying universal constructor.

Details

The distance between the two construction lanes in the linear propagator is separated by nine half diagonals (abbreviated 9hd). Also, construction-arm recipes could only be used if they were made up of pairs of gliders, one on each of the two lanes. No singleton gliders could be allowed, because of the way that semi-Snarks were used to place gliders on the two output lanes. This style of construction arm was an early predecessor of single channel construction arms. Besides the linear propagator it was used in only a few patterns, mainly the earliest spiral growth pattern.

The construction information is carried by the first two gliders in each set of four in the memory loop. The last two gliders have no timing constraints; their only purpose is to reset the constructor-arm circuit.

Three versions of the linear propagator were posted. In all three versions, the memory loop period was a multiple of 277. A descendant replicator will eventually match the original ancestor's phase, and this will happen as soon as possible -- but even in the smallest version, this won't be for several hundred thousand replication cycles (!)

First version

The first version was period 237228340, and it ran the most quickly in Golly because the glider stream was not folded over on itself any more than necessary; each glider in the recipe spent most of its time traveling through empty space, with no nearby gliders moving in the other direction. (Nearby boustrophedonic gliders enormously increase the number of hashtiles that the HashLife algorithm has to memoize to be able to run a pattern quickly.)

This version had a huge bounding box 14826990 × 14826908 -- and needed the largest number of ticks to complete a replication cycle. But in Golly it runs much faster than the other versions. Golly runs fastest when all the gliders are stretched out in a single line heading NW or SE.

The population starts out at 290096 ON cells, almost all gliders. After one cycle of 237228340 ticks, the replicator will return to its original state, and a second copy will have been created directly to the north, offset by (0,-256). The only difference between parent and child is the 277-tick delay -- so for the first four replication cycles the population will be an exact multiple of its original value.

Second version

The second version was period p118614724 -- slower to simulate, but smaller and lower-period. The bounding box was reduced by half by doubling over the glider stream on itself. This means that gliders in this version are constantly passing each other at close range. The number of hashtiles goes up exponentially, and so the pattern runs much slower in Golly, even though the replication cycle completes in half the number of ticks.

Third version

In the last, period-88965198 design, the non-coding gliders were removed completely, so the first half of the recipe is interleaved with the second half. The first half-recipe uses the second half-recipe's gliders to reset the semi-Snarks, and then the second half-recipe in turn re-uses the first half-recipe's gliders as reset gliders.

The bounding box goes down to 3707102x3707020, marginally smaller than a Gemini spaceship, but the gliders now need three trips around the memory loop to complete a replication cycle -- two passes for the BUILD stage and one more pass for the COPY stage.

The linear propagator ranked third place in the Pattern of the Year 2013 competition in a belated vote held on the ConwayLife.com forums, tied with the CC semi-Snark, and behind the loafer and the Snark.

External links

• Linear propagator at the Life Lexicon